package LeetCode;

/**
 * @Author: Dijah
 * @Date: 2022/12/20 13:41
 * @Desc:
 */
public class code124_maxPathSum {

    public static class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(){}
        TreeNode(int val){this.val = val;}
        TreeNode(int val,TreeNode left,TreeNode right){
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    static int sum = Integer.MIN_VALUE;
    public static int maxPathSum(TreeNode root) {
        //可以使用后续遍历的方式
        getMax(root);
        return sum;
    }

    public static int getMax (TreeNode r){
        if(r == null){
            return 0;
        }
        int left = Math.max(0,getMax(r.left));
        int right = Math.max(0,getMax(r.right));
        sum = Math.max(sum,left + right + r.val);
        return Math.max(left,right) + r.val;
    }

    public static void main(String[] args) {
        TreeNode treeNode = new TreeNode(-10);
        TreeNode treeNode1 = new TreeNode(9);
        TreeNode treeNode2 = new TreeNode(20);
        TreeNode treeNode3 = new TreeNode(15);
        TreeNode treeNode4 = new TreeNode(7);
        TreeNode treeNode5 = new TreeNode(2);

        treeNode.left = treeNode1;
        treeNode.right = treeNode2;
        treeNode2.left = treeNode3;
        treeNode2.right = treeNode4;
        treeNode3.left = treeNode5;
        maxPathSum(treeNode);
    }


}
